package project.euler.honk.problem.to200;

class Problem187 {

	private final static int SIZE = 100000000;
	private final int[] knownValues = new int[SIZE];

	private Problem187() {
		knownValues[1] = 1;
	}

	private int check(int number, int count) {
		if (knownValues[number] != 0)
			return knownValues[number] + count;
		int max = (int) Math.sqrt(number) + 1;
		for (int i = 2; i < max; i++) {
			if (number % i == 0) {
				int x = 1 + check(number / i, count + 1);
				knownValues[number] = x;
				return x;
			}
		}
		return 1;
	}

	public static void main(String[] args) {
		Problem187 p = new Problem187();
		long start = System.currentTimeMillis();
		int count = 0;
		for (int i = 2; i < SIZE; i++) {
			if (p.check(i, 0) == 2) {
				count++;
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("Result: " + count + "\tTime: " + (end - start));
	}
}